﻿// sampleCode_SuffixArray.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1000;
int n, k;
int rankA[MAX_N + 1];
int tmp[MAX_N + 1];

bool compare_sa(int i, int j) {
    if (rankA[i] != rankA[j]) return rankA[i] < rankA[j];
    else {
        int ri = i + k <= n ? rankA[i + k] : -1;
        int rj = j + k <= n ? rankA[j + k] : -1;
        return ri < rj;
    }
}

//计算字符串S的后缀数组
void construct_sa(string S, int* sa) {
    n = S.length();
    //初始化长度为1 rank直接取字符的编码
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rankA[i] = i <n ? S[i]:-1;
    }
    
    //利用对长度为k的排序的结果对长度为2k的排序
    for (k = 1; k <= n; k *= 2) {
        sort(sa, sa + n + 1, compare_sa);

        //先在tmp中临时存储新计算的rank 再转存回rank中
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            rankA[i] = tmp[i];
        }
    }
}


int main()
{
    std::cout << "Hello World!\n";
}

 